package algotithm.weekendrace.leetcode283.test3;

/**
 * @author tom
 * @date 2022-03-06 14:48
 */

import java.util.HashMap;
import java.util.Map;
/* Definition for a binary tree node.
        * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
 class TreeNode {
     int val;
     TreeNode left;
     TreeNode right;
     TreeNode() {}
     TreeNode(int val) { this.val = val; }
     TreeNode(int val, TreeNode left, TreeNode right) {
         this.val = val;
         this.left = left;
         this.right = right;
     }
 }
class Solution {
    public TreeNode createBinaryTree(int[][] descriptions) {
        // 缓存TreeNode节点
        Map<Integer, TreeNode> map = new HashMap<>();
        DSU dsu = new DSU(100001);
        for (int[] d : descriptions) {
            TreeNode node1 = map.compute(d[0], (key, value) -> value == null ? new TreeNode(d[0]) : value);
            TreeNode node2 = map.compute(d[1], (key, value) -> value == null ? new TreeNode(d[1]) : value);
            if (d[2] ==1) {
                node1.left = node2;
            } else {
                node1.right = node2;
            }
            dsu.union(d[1], d[0]);
        }
        // 随便找一个节点即可，因为全部处理之后，所有节点的parent都是根节点
        return map.get(dsu.find(descriptions[0][0]));
    }

    class DSU {
        int[] parent;

        public DSU(int N) {
            parent = new int[N];
            for (int i = 0; i < N; ++i) {
                parent[i] = i;
            }
        }

        public int find(int x) {
            if (parent[x] != x) {
                parent[x] = find(parent[x]);
            }
            return parent[x];
        }

        public void union(int x, int y) {
            parent[find(x)] = find(y);
        }
    }
}
